1. Field of the Invention
The present invention relates to calculation techniques for solving simultaneous linear equations.
2. Description of the Related Art
It is known that many problems to be solved in a variety of fields are reduced down to simultaneous linear equations by discrete approximation methods or the like.
Such simultaneous linear equations usually have regular coefficient matrices, and thus can be solved by Gaussian elimination. If a coefficient matrix is large and sparse, iterative methods, such as the Jacobi method and the Gauss-Seidel iteration method, and a conjugate gradient method (hereinafter abbreviated as “CG method”) are known to be effective (see, Mori, Sugihara, and Murota: “Numerical calculations (in Japanese),” Iwanami Koza Oyo Sugaku [Hoho 2], Iwanami Shoten (1994)). The following techniques are disclosed since the specifications of calculators and the speed of calculation vary depending on which solution method is selected to solve the problem.
Japanese Patent Laid-Open No. 05-073527 discloses a method in which one of either a direct method or an iterative method is selected to solve a set of simultaneous linear equations, depending on whether or not its matrix is sparse and whether or not the frequency of a power source is below a predetermined parameter. This Japanese Patent Laid-Open No. 05-073527 states that the disclosed method allows the selection of the best solution method according to the amount of memory.
Japanese Patent Laid-Open No. 11-242664 discloses a method that involves a step of estimating the time required for solving a problem and allows the best solution method to be selected, on the basis of the estimated time, from a plurality of trigonometric resolution methods available for matrices. This Japanese Patent Laid-Open No. 11-242664 states that the disclosed method enables a given problem to be solved at the highest speed.
However, there are cases where a coefficient matrix is singular, depending on the problem to be solved. In such cases, the Gauss method, which is a type of a direct method, and a series of iterative methods based on the Jacobi method fail.
On the other hand, it is known that if certain conditions are met, the CG method can give a solution even if a coefficient matrix is singular (see, E. F. Kaasschieter: “Preconditioned conjugate gradients for solving singular systems,” Journal of Computational and Applied Mathematics, 24, pp. 265-275 (1988)). It is also known that even in the case where the CG method fails, a conjugate residual method (hereinafter abbreviated as “CR method”) does not fail and converges to the optimal solution (see, Abe, Ogata, Sugihara, Zhang, and Mitsui: “Convergence of CR method for simultaneous linear equations with singular coefficient matrices (in Japanese),” Transactions of the Japan Society for Industrial and Applied Mathematics, Vol. 9, No. 1, pp. 1-13 (1999)).
To sum up, when a coefficient matrix is regular, direct methods, iterative methods, the CG method, and the CR method are all effective. When a coefficient matrix is singular, the CG method and the CR method are effective if certain conditions are met, and otherwise only the CR method is effective.
However, since solution methods vary depending on whether the coefficient matrix is regular or singular, a solution method for simultaneous linear equations cannot be determined in advance if it is not known whether or not the coefficient matrix of the equations to be solved is regular.